package linked;

public class LinkedList {
    static class Node{
        long val;
        Node prev;
        Node next;

        public Node(long val) {
            this.val = val;
        }
    }

    public Node head;
    public Node last;
    public int size;
    public int size() {
        return size;
    }











    public void add(int index,long val){
        if(head == null){
            head = last = new Node(val);
            size++;
            return ;
        }

        if(index < 0 || index > size) return ;
        Node node = new Node(val);
        Node cur = head;
        Node prev = null;

        while(index > 0){
            prev = cur;
            cur = cur.next;
            index--;
        }
        if(prev == null){// 头插
            node.next = head;
            head.prev = node;
            head = node;
            size++;
            return ;
        }

        prev.next = node;
        node.prev = prev;
        node.next = cur;
        cur.prev = node;
        size++;
    }

    public void add(long val){
        if(last == null){
            head = last = new Node(val);
            size++;
            return ;
        }
        Node node = new Node(val);
        node.prev = last;
        last.next = node;
        last = last.next;
        size++;
        return ;
    }


    public long remove(int index){
        if(index < 0 || index > size - 1){
            throw new ArrayIndexOutOfBoundsException("index : " + index);
        }

        Node prev = null;
        Node cur = head;

        while(index > 0){
            prev = cur;
            cur = cur.next;
            index--;
        }

        long res = cur.val;

        if(prev == null){// 删除头节点
            head = cur.next;
            head.prev = null;
        }else { //删除 中间或者末尾节点
            prev.next = cur.next;
            if(cur.next != null) {
                cur.next.prev = prev;
            } else{// 删除的是尾部
                last = prev;
            }

        }
        size--;
        return res;
    }



    // 检查一个对象是否正确
    public void check() {
        if (size == 0) {
            if (head != null) {
                throw new RuntimeException();
            }
            if (last != null) {
                throw new RuntimeException();
            }
        } else if (size == 1) {
            if (head != last) {
                throw new RuntimeException();
            }

            if (head == null) {
                throw new RuntimeException();
            }
        } else {
            // 1. 检查 size 是否正确
            int actualSize = calcSize(head);
            if (size != actualSize) {
                throw new RuntimeException();
            }

            // 2. 检查头结点
            if (head == null) {
                throw new RuntimeException();
            }
            if (head.prev != null) {
                throw new RuntimeException();
            }
            if (head.next.prev != head) {
                throw new RuntimeException();
            }
            // 3. 检查尾结点
            if (last == null) {
                throw new RuntimeException();
            }
            if (last.next != null) {
                throw new RuntimeException();
            }
            if (last.prev.next != last) {
                throw new RuntimeException();
            }
            // 4. 检查剩余结点
            Node cur = head.next;
            while (cur != last) {
                if (cur.next.prev != cur) {
                    throw new RuntimeException();
                }
                if (cur.prev.next != cur) {
                    throw new RuntimeException();
                }

                cur = cur.next;
            }
        }
    }


    private int calcSize(Node head) {
        int s = 0;
        for (Node cur = head; cur != null; cur = cur.next) {
            s++;
        }
        return s;
    }
}
